﻿#pragma once
#include "Index.h"

/**
 * 删除排序链表中的重复元素 II
 * https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/
 *
 * 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
 * 如: 输入 [1,2,3,3,4,4,5] => 输出 [1,2,5]
 */
namespace DeleteListDuplicateExclude
{
    class Question { public: virtual ListNode* deleteDuplicates(ListNode* head)=0; };

    class Solution:public Question
    {
    public:
        ListNode* deleteDuplicates(ListNode* head) override
        {
            if(!head)
                return nullptr;

            ListNode dummy;
            dummy.next=head;

            ListNode* pre=&dummy;
            ListNode* cur=head;
            ListNode* tail=cur->next;

            while(tail)
            {
                bool find_duplicate=false;
                while(tail && tail->val==cur->val)
                {
                    find_duplicate=true;
                    tail=tail->next;
                }

                if(find_duplicate)
                {
                    pre->next=tail;
                    cur=pre->next;
                    tail=cur?cur->next:nullptr;
                }
                else
                {
                    pre=pre->next;
                    cur=cur->next;
                    tail=tail->next;
                }
            }

            return dummy.next;
        }
    };


    TEST(Test,DuplicateAtListHead)
    {
        TEST_SOLUTION1(Question,Solution,&)
        {
            auto input_list= ListUtil::createListFromFormat("[1,1,2,3,3,3,4,4,5,7,7,7]");
            auto output_list= solution->deleteDuplicates(input_list);
            EXPECT_TRUE(ListUtil::isEqual(output_list,"2,5"));
        };
    }
};
